package datastruct;

import java.util.*;

public class GetSkyLine {

    /**
     * LeetCode T218 天际线问题
     *
     * 总结：用到扫描线算法
     * @param args
     */
    public static void main(String[] args) {

    }

    public List<List<Integer>> getSkyline(int[][] buildings) {
        //将所有边界放入链表中
        List<int[]> boundaries = new ArrayList<>();
        for (int[] building : buildings){
            //左边界
            boundaries.add(new int[]{building[0], -building[2]});
            //右边界
            boundaries.add(new int[]{building[1], building[2]});
        }
        Collections.sort(boundaries, (a, b) ->{
            if (a[0] != b[0])
                return a[0] - b[0];
            return a[1] - b[1];
        });
        int pre = 0;
        List<List<Integer>> ans = new ArrayList<>();
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) ->b - a);
        queue.offer(0);
        for (int[] boundary : boundaries) {
            if (boundary[1] < 0){
                queue.add(-boundary[1]);
            } else {
                queue.remove(boundary[1]);
            }

            int cur = queue.peek();
            if (cur != pre){
                List<Integer> list = new ArrayList<>();
                list.add(boundary[0]);
                list.add(cur);
                ans.add(list);
                pre = cur;
            }
        }
        return ans;

    }
}
